// 给定一个m * n的有序二维矩阵matrix，矩阵中每行元素从左到右升序排列，每行的第一个整数大于前一行的最后一个整数，
// 再给定一个目标值target，要求判断矩阵中是否存在目标值target

// 思路，先找到行列的较小值， 先对角线二分查找，然后在横向和纵向查找

function searchMatrix(matrix, target) {
    let rowLength = matrix.length
    if (rowLength === 0) {
        return false
    }
    let colLength = matrix[0].length
    if (colLength === 0) {
        return false
    }
    let min = Math.min(rowLength, colLength)
    let index = diagonalBinarySearch(matrix, min - 1, target)
    if (matrix[index][index] === target) {
        return true
    }
    for (let i = 0; i <= index; i++) {
        let rowResult = rowBinarySearch(matrix, i, colLength - 1, target)
        let colResult = colBinarySearch(matrix, i, rowLength - 1, target)
        if (rowResult || colResult) {
            return true
        }        
    }
    return false

}

function diagonalBinarySearch(matrix, diagonal, target) {
    let left = 0
    let right = diagonal
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (matrix[mid][mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

function rowBinarySearch(matrix, begin, cols, target) {
    let left = begin
    let right = cols
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        if (matrix[begin][mid] < target) {
            left = mid + 1
        } else if (matrix[begin][mid] > target) {
            right = mid - 1
        } else {
            return true
        }
    }
}

function colBinarySearch(matrix, begin, rows, target) {
    let left = begin
    let right = rows
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        if (matrix[mid][begin] < target) {
            left = mid + 1
        } else if (matrix[mid][begin] > target) {
            right = mid - 1
        } else {
            return true        
        }
    }
}

let matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]

let matrix2 = [
    [1,4,7,11,15],
    [2,5,8,12,19],
    [3,6,9,16,22],
    [10,13,14,17,24],
    [18,21,23,26,30]
], target = 16

// console.log(searchMatrix(matrix, 5))

let metrix3 = [
    [1,4,7,11,15],
    [2,5,8,12,19],
    [3,6,9,16,22],
    [10,13,14,17,24],
    [18,21,23,26,30]
]
let target3 = 20
// console.log(searchMatrix(matrix2, target))
console.log(searchMatrix(metrix3, target3))


// 题意表明每行的元素从左到右升序排列，每列的元素从上到下升序排列。
// 因此以左下角为起点，向上数值减小，向右数值增大，利用此特点查找值

var searchMatrix = function(matrix, target) {
    if(matrix === null || matrix.length === 0 || matrix[0].length === 0) return false;
    let col = 0;
    let row = matrix[0].length - 1;
    while(col < matrix.length && row >=0) {
        if(matrix[col][row] > target) {
            row--;
        }  else if(matrix[col][row] < target) {
            col++
        } else {
            return true;
        }
    }
    return false;
};

var searchMatrix2 = function(matrix, target) {
    if(matrix === null || matrix.length === 0 || matrix[0].length === 0) return false;
    let row = matrix.length - 1;
    let col = 0;
    while (row >= 0 && col < matrix[0].length) {
        if (matrix[row][col] > target) {
            row--;
        } else if (matrix[row][col] < target) {
            col++;
        } else {
            return true;
        }
    }
    return false;
};